/**
 * Created by L.jp
 * Description:输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。
 * User: 86189
 * Date: 2022-05-12
 * Time: 17:38
 */
//要求：空间复杂度 O(1)，时间复杂度 O(n)
//class ListNode {
//    int val;
//    ListNode next = null;
//
//    ListNode(int val) {
//        this.val = val;
//    }
//
//    @Override
//    public String toString() {
//        return "ListNode{" + "val=" + val + ", next=" + next + '}';
//    }
//}
public class Solution {
    public static ListNode Merge(ListNode list1,ListNode list2) {
        //方法一：迭代：
        ListNode res=new ListNode(-1);
        ListNode cur=res;
        ListNode cur1=list1;
        ListNode cur2=list2;
        while (cur1!=null && cur2!=null){
            if(cur1.val<cur2.val){
                cur.next=cur1;
                cur1=cur1.next;
                cur=cur.next;
            }else{
                cur.next=cur2;
                cur2=cur2.next;
                cur=cur.next;
            }
        }
        if (cur1!=null){
            cur.next=cur1;
        }
        if (cur2!=null){
            cur.next=cur2;
        }
        return res.next;
    }
    
    public static void main(String[] args) {
        ListNode list1=new ListNode(1);
        ListNode list2=new ListNode(2);
        int val2= list2.val;
        int val=list1.val;
        for(int i = 0;i<3;i++){
            list1.next = new ListNode(val+2);
        }
        for(int i = 0; i < 3; i++){
            list2.next=new ListNode(val2+2);
        }
        System.out.println(Merge(list1, list2));
    }
}
